package com.berchen.数据结构.图;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 图
 */
public class Graph {
    private ArrayList<String> vertex;   // 存储顶点集合
    private int[][] edges;  // 存储图对应的邻接矩阵
    private int numOfEdges; // 表示边的个数
    private int [] visited;// 表示节点是否访问过
    private int depthIndex; // 深度遍历的行

    /**
     * 广度优先遍历 图
     */
    public void breadthFirst(){
        visited=new int[edges.length];
        for(int i =0;i<edges.length;i++){
            breadthFirst(i);
        }
    }

    /**
     *
     * @param i 行索引
     */
    public void breadthFirst(int i){
        if(visited[i]!=1) {
            visited[i] = 1;
            System.out.print(vertex.get(i)+"-->");
        }
        for(int j =0;j<edges[i].length;j++){
            if(edges[i][j]==1&&visited[j]!=1){
                visited[j]=1;
                System.out.print(vertex.get(j)+"-->");
            }
        }
    }


    /**
     * 深度优先遍历 图
     */
    public void depthFirst(){
        visited=new int[edges.length];
        for(int i =0;i<edges.length;i++){
            depthIndex=i;   // 记录本层深度
            depthFirst(i);
        }
    }

    /**
     * 行
     * @param i 行索引
     */
    private void depthFirst(int i){
        if(visited[i]!=1) {
            visited[i] = 1;
            System.out.print(vertex.get(i)+"-->");
        }
        for(int j =0;j<edges[i].length;j++){
            if(edges[i][j]==1&&visited[j]!=1) {
                depthFirst(j);
                if (i != depthIndex) {  // 如果是该层 说明该 I-j 的深度已经走完了 应该走 i-j+1 节点的深度了 就不需要break 不满足该条件说明不是i-j这一层
                    break;
                }
            }
        }
    }


    /**
     * @param n 顶点个数
     */
    public Graph(int n) {
        edges=new int[n][n];
        vertex=new ArrayList<>(n);
        numOfEdges=0;
    }

    /**
     * 插入顶点
     * @param vertexStr
     */
    public void insertVertex(String vertexStr){
        vertex.add(vertexStr);
    }

    /**
     * 添加边
     * @param v1    顶点索引
     * @param v2    顶点索引
     * @param weight 权重 0 不连通 1 连通
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        numOfEdges++;
    }

    /**
     * 显示矩阵
     */
    public void showGraph(){
        System.out.println("  "+Arrays.toString(vertex.toArray()));
        int count=0;
        for(int[] i:edges){
            System.out.println(vertex.get(count++)+" "+Arrays.toString(i));
        }
    }

    /**
     * 返回 v1 v2 的权重
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    /**
     * 返回节点index 对应的数据
     * @param index
     * @return
     */
    public String getValueByIndex(int index){
        return vertex.get(index);
    }
    /**
     * 得到顶点数目
     * @return
     */
    public int getNumOfVertex(){
        return vertex.size();
    }
    /**
     * 得到边的数目
     * @return
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }
}
